Để định nghĩa khái niệm PAC-học được, trước hết cần định nghĩa một số khái niệm liên quan.[2][3]

Để minh họa cho định nghĩa, ta sẽ sử dụng hai ví dụ. Ví dụ thứ nhất là bài toán nhận dạng chữ viết được cho dưới dạng một mảng n {\displaystyle n} bit. Ví dụ thứ hai là bài toán tìm một khoảng xếp loại sao cho các điểm trong khoảng là dương tính và ngoài khoảng là âm tính.

Đặt X {\displaystyle X} là tập hợp tất cả các mã hóa của các mẫu, gọi là không gian trường hợp, và mỗi trường hợp có một độ dài nhất định. Trong bài toán nhận dạng chữ viết, không gian trường hợp là X = { 0 , 1 } n {\displaystyle X=\{0,1\}^{n}} . Trong bài toán khoảng, không gian trường hợp là X = R {\displaystyle X=\mathbb {R} } , trong đó R {\displaystyle \mathbb {R} } là tập hợp số thực.

Một khái niệm là một tập hợp con c ⊂ X {\displaystyle c\subset X} . Trong ví dụ nhận dạng chữ viết, một khái niệm có thể là tập hợp tất cả các mã hóa của chữ cái "P" trong X = { 0 , 1 } n {\displaystyle X=\{0,1\}^{n}} . Trong ví dụ tìm khoảng, một khái niệm có thể là khoảng từ π / 2 {\displaystyle \pi /2} đến 10 {\displaystyle {\sqrt {10}}} . Một lớp khái niệm C {\displaystyle C} là một tập hợp các khái niệm trên tập X {\displaystyle X} . Trong ví dụ nhận dạng chữ viết, đây có thể là tập hợp các tập hợp con gồm các dãy bit mã hóa các nét vẽ có độ rộng bằng 1.

Đặt E X ( c , D ) {\displaystyle EX(c,D)} là một thủ tục trả về một mẫu x {\displaystyle x} phân phối theo một phân bố xác suất D {\displaystyle D} và đồng thời cũng trả về c ( x ) {\displaystyle c(x)} , bằng 1 nếu x ∈ c {\displaystyle x\in c} và 0 trong trường hợp còn lại.

Giả sử tồn tại thuật toán A {\displaystyle A} sao cho khi thuật toán được gọi thủ tục E X ( c , D ) {\displaystyle EX(c,D)} và cung cấp các giá trị ϵ {\displaystyle \epsilon } và δ {\displaystyle \delta } thì, với xác suất ít nhất 1 − δ {\displaystyle 1-\delta } , A {\displaystyle A} trả về một giả thuyết h ∈ C {\displaystyle h\in C} có lỗi tổng quát hóa nhỏ hơn hoặc bằng ϵ {\displaystyle \epsilon } khi các mẫu trong X {\displaystyle X} được phân phối theo phân bố D {\displaystyle D} . Nếu tồn tại thuật toán như vậy cho mọi khái niệm c ∈ C {\displaystyle c\in C} , mọi phân bố D {\displaystyle D} trên X {\displaystyle X} , và mọi 0 < ϵ < 1 / 2 {\displaystyle 0<\epsilon <1/2} và 0 < δ < 1 / 2 {\displaystyle 0<\delta <1/2} thì C {\displaystyle C} là PAC-học được (hay PAC-học được không phụ thuộc phân bố). Ta cũng gọi A {\displaystyle A} là một thuật toán học PAC của C {\displaystyle C} .

Một thuật toán chạy trong thời gian t {\displaystyle t} nếu nó dùng không quá t {\displaystyle t} mẫu và chạy trong không quá t {\displaystyle t} bước. Một lớp khái niệm là PAC-học được hiệu quả nếu nó là PAC-học được bởi một thuật toán chạy trong thời gian đa thức của 1 / ϵ {\displaystyle 1/\epsilon } , 1 / δ {\displaystyle 1/\delta } và chiều dài mỗi trường hợp.